// #define print(...)

class Solution {
public:
    string frequencySort(string s) {
        map<char,int> counter;
        int maxLen = 0;
        for(auto & c : s){
            maxLen = max(++counter[c], maxLen);
        }

        vector<string> bucket(maxLen, "");
        for(auto &[c,n] : counter)
            bucket[n-1].append(1, c);

        string sorted;
        for(int n=maxLen; n>0; n--){
            for(auto c:bucket[n-1])
                sorted.insert(sorted.end(), n, c);
        }
        return sorted;
    }
};
